Search results for "Quantum Turing machine"

showing 3 items of 3 documents

Quantum Computation With Devices Whose Contents Are Never Read

2010

In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines using sublogarithmic amounts of read/write memory are shown to…

FOS: Computer and information sciencesQuantum sortQuantum PhysicsTheoretical computer scienceQuantum Turing machineComputer scienceFormal Languages and Automata Theory (cs.FL)ComputationQuantum simulatorFOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputational Complexity (cs.CC)Computer Science - Computational ComplexityQuantum algorithmQuantum informationComputational problemQuantum Physics (quant-ph)Quantum computer
researchProduct

Quantum Real - Time Turing Machine

2001

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineDTIMEComputer scienceProbabilistic Turing machine2-EXPTIMESuper-recursive algorithmComputationDescription numberDSPACElaw.inventionsymbols.namesakeTuring machineTuring completenessNon-deterministic Turing machinelawAlgorithm characterizationsQuantumPSPACEQuantum computerFinite-state machineTuring machine examplesNSPACETheoryofComputation_GENERALAutomatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring reductionTheory of computationsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineComputer Science::Formal Languages and Automata TheoryRegister machine
researchProduct

Space-Efficient 1.5-Way Quantum Turing Machine

2001

1.5QTM is a sort of QTM (Quantum Turing Machine) where the head cannot move left (it can stay where it is and move right). For computations is used other - work tape. In this paper will be studied possibilities to economize work tape space more than the same deterministic Turing Machine can do (for some of the languages). As an example language (0i1i|i ≥ 0) is chosen, and is proved that this language could be recognized by deterministic Turing machine using log(i) cells on work tape , and 1.5QTM can recognize it using constant cells quantity.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineSuper-recursive algorithmComputer scienceProbabilistic Turing machineComputationDescription numberMultitape Turing machineDSPACElaw.inventionTuring machinesymbols.namesakeNon-deterministic Turing machinelawAlgorithm characterizationsPSPACEWolfram's 2-state 3-symbol Turing machineTuring machine examplesNSPACETuring reductionsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineRegister machine
researchProduct